package Leetcode.树;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

/**
 * @Author kirito
 * @Date 2023/12/15 10:22
 * @PackageName:Leetcode.树
 * @ClassName: 反转二叉树的奇数层
 * @Description:
 * 给你一棵 完美 二叉树的根节点 root ，请你反转这棵树中每个 奇数 层的节点值。
 *
 * 例如，假设第 3 层的节点值是 [2,1,3,4,7,11,29,18] ，那么反转后它应该变成 [18,29,11,7,4,3,1,2] 。
 * 反转后，返回树的根节点。
 *
 * 完美 二叉树需满足：二叉树的所有父节点都有两个子节点，且所有叶子节点都在同一层。
 *
 * 节点的 层数 等于该节点到根节点之间的边数。
 * @Version 1.0
 */
public class 反转二叉树的奇数层 {
    /**
     * 同样的方法我们还可以使用深度优先搜索来遍历该二叉树，对奇数层进行反转.遍历过程如下！
     * 由于该二叉树是完美二叉树，因此我们可以知道对于根节点来说，它的孩子节点为第一层节
     * 点，此时左孩子需要与右孩子需要进行反转；
     * 当遍历每一层时，由于根，根；分别指向该层两个可能需要进行值交换的节点.根据完
     * 美二叉树的层次反转规则，即左边排第一的元素与倒数第一元素进行交换，第二个元素与倒
     * 数二个元素交换，此时根的左孩子与根的右孩子可能需要进行交换根的右孩
     * 子与Oot；的左孩子可能需要进行交换.在遍历的同时按照上述规则，将配对的节点进行递
     * 归传递到下一层；
     * 我们用isodd来标记当前层次是否为奇数层，由于偶数层不需要进行交换，当isodd为
     * 块菌时，表明当前需要交换，我们直接交换两个节点rooti，根；的值；
     * 由于完美二叉树来说，第的节点数目要么为21个，要么为0个，因此如果最左边的节点
     * 根为空时，则可以直接返回
     */
    public TreeNode reverseOddLevels(TreeNode root) {
        dfs(root.left, root.right, true);
        return root;
    }

    private void dfs(TreeNode root1, TreeNode root2, boolean isOdd) {
        if (root1 == null) {
            return;
        }
        if (isOdd) {
            int temp = root1.val;
            root1.val = root2.val;
            root2.val = temp;
        }
        dfs(root1.left, root2.right, !isOdd);
        dfs(root1.right, root2.left, !isOdd);
    }

    /**
     * 我们直接按照层次遍历该二叉树，然后将奇数层中的值进行反转。二叉树按照层次遍历是一个基本的广度优先搜索问题，
     * 可以参考「树的层序遍历」。在遍历的同时，对每一层进行标记，如果当前该层为奇数层，
     * 则将该层中的节点用数组保存起来，然后将该层所有节点的值进行反转即
     */
    public TreeNode reverseOddLevels2(TreeNode root) {
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        boolean isOdd = false;
        while (!queue.isEmpty()) {
            int sz = queue.size();
            List<TreeNode> arr = new ArrayList<>();
            for (int i = 0; i < sz; i++) {
                TreeNode  node = queue.poll();
                if (isOdd) {
                    arr.add(node);
                }
                if (node.left != null) {
                    queue.offer(node.left);
                    queue.offer(node.right);
                }
            }
            if (isOdd) {
                for (int l = 0, r = sz - 1; l < r; l++, r--) {
                    int temp = arr.get(l).val;
                    arr.get(l).val = arr.get(r).val;
                    arr.get(r).val = temp;
                }
            }
            isOdd ^= true;
        }
        return root;
    }
}